/******************************************************************************
                         COPYRIGHT 1955-2009 by BUPT ISC.
                        北京邮电大学信息安全中心 版权所有
                           Web: http://www.bupt.edu.cn
 *******************************************************************************/
/*******************************************************************************
  文件名： timers.c
  项目：   
  模块：   timers
  作者：   zhuxiaobo
  版本：   0.1
  创建于:  2009-04-13 
  描述：
    计时器表的实现 

  修改历史： 
  日期：     修改人：     修改描述：
  
 *********************************************************************************/

#include <sys/types.h>

#include <stdlib.h>
#include <stdio.h>
#include <syslog.h>

#include "timers.h"


/******************************************************************************
  函数名：hash
  功能描述：
    计算特定定时器到的hash值 

  输入参数：
   TIMERS *pstTable 定时器表 
   TIMER  *pstTemp  特定的定时器

  输出参数：
    无

  返回值：
   int 计算出的hash值 
 *****************************************************************************/
static unsigned int hash( TIMERS *pstTable, TIMER *pstTemp )
{
    /* We can hash on the trigger time, even though it can change over
     ** the life of a timer via either the iPeriodic bit or the resetTmr()
     ** call.  This is because both of those guys call resortLink(), which
     ** recomputes the hash and moves the timer to the appropriate list.
     */
    return (
            (unsigned int) pstTemp->stTime.tv_sec ^
            (unsigned int) pstTemp->stTime.tv_usec ) % pstTable->iSize;
}



/******************************************************************************
  函数名：addLink
  功能描述：
    同一个hash值的定时器以链表形式保存,加入的时候对定时器进行了插入排序 

  输入参数：
    TIMERS *pstTable 定时器表  
    TIMER  *pstTemp  定时器

  输出参数：
    无

  返回值：
    无
 *****************************************************************************/
static void addLink(TIMERS *pstTable,  TIMER* pstTemp )
{
    int h = pstTemp->iHash;
    TIMER* pstTemp2;
    TIMER* pstTemp2Prev;

    pstTemp2 = pstTable->pstTimersTable[h];
    if ( pstTemp2 == (TIMER*) 0 )
    {
        /* The list is empty. */
        pstTable->pstTimersTable[h] = pstTemp;
        pstTemp->pstPrev = pstTemp->pstNext = (TIMER*) 0;
    }
    else
    {
        if ( pstTemp->stTime.tv_sec < pstTemp2->stTime.tv_sec ||
                ( pstTemp->stTime.tv_sec == pstTemp2->stTime.tv_sec &&
                  pstTemp->stTime.tv_usec <= pstTemp2->stTime.tv_usec ) )
        {
            /* The new timer goes at the head of the list. */
            pstTable->pstTimersTable[h] = pstTemp;
            pstTemp->pstPrev = (TIMER*) 0;
            pstTemp->pstNext = pstTemp2;
            pstTemp2->pstPrev = pstTemp;
        }
        else
        {
            /* Walk the list to find the insertion point. */
            for ( pstTemp2Prev = pstTemp2, pstTemp2 = pstTemp2->pstNext; pstTemp2 != (TIMER*) 0;
                    pstTemp2Prev = pstTemp2, pstTemp2 = pstTemp2->pstNext )
            {
                if ( pstTemp->stTime.tv_sec < pstTemp2->stTime.tv_sec ||
                        ( pstTemp->stTime.tv_sec == pstTemp2->stTime.tv_sec &&
                          pstTemp->stTime.tv_usec <= pstTemp2->stTime.tv_usec ) )
                {
                    /* Found it. */
                    pstTemp2Prev->pstNext = pstTemp;
                    pstTemp->pstPrev = pstTemp2Prev;
                    pstTemp->pstNext = pstTemp2;
                    pstTemp2->pstPrev = pstTemp;
                    return;
                }
            }
            /* Oops, got to the end of the list.  Add to tail. */
            pstTemp2Prev->pstNext = pstTemp;
            pstTemp->pstPrev = pstTemp2Prev;
            pstTemp->pstNext = (TIMER*) 0;
        }
    }
}


/******************************************************************************
  函数名：removeLink
  功能描述：
  从链表中去除此节点 

  输入参数：
    TIMERS *pstTable 定时器表  
    TIMER  *pstTemp  定时器

  输出参数：
    无

  返回值：
    无
 *****************************************************************************/
static void removeLink( TIMERS *pstTable, TIMER* pstTemp )
{
    int h = pstTemp->iHash;

    if ( pstTemp->pstPrev == (TIMER*) 0 )
        pstTable->pstTimersTable[h] = pstTemp->pstNext;
    else
        pstTemp->pstPrev->pstNext = pstTemp->pstNext;
    if ( pstTemp->pstNext != (TIMER*) 0 )
        pstTemp->pstNext->pstPrev = pstTemp->pstPrev;
}

/******************************************************************************
  函数名：resortLink
  功能描述：
  对某个定时器节点进行重新排序 

  输入参数：
    TIMERS *pstTable 定时器表  
    TIMER  *pstTemp  定时器

  输出参数：
    无

  返回值：
    无
 *****************************************************************************/
static void resortLink(TIMERS *pstTable, TIMER* pstTemp )
{
    /* Remove the timer from its old list. */
    removeLink(pstTable, pstTemp );
    /* Recompute the hash. */
    pstTemp->iHash = hash(pstTable, pstTemp );
    /* And add it back in to its new list, sorted correctly. */
    addLink(pstTable, pstTemp );
}


/******************************************************************************
  函数名：initTmr
  功能描述：
  初始化定时器,并确定计时器hash表的大小

  输入参数：
    TIMERS *pstTable 定时器表  
    int    iSize     定时器hash表大小

  输出参数：
    无

  返回值：
    无
 *****************************************************************************/

void initTmr(TIMERS *pstTable, int iSize )
{
    int h;

    if (pstTable == NULL)
    {
        printf("pstTable haven't space\n");
        return;
    }
    pstTable->pstTimersTable = (TIMER **)malloc(iSize * sizeof(TIMER *));

    if (pstTable->pstTimersTable == NULL)
    {
        printf("pstTimersTable malloc failed\n");
        return;
    }

    for ( h = 0; h < iSize; ++h )
        pstTable->pstTimersTable[h] = (TIMER*) 0;
    pstTable->pstFreeTimers = (TIMER*) 0;
    pstTable->iSize = iSize;
    pstTable->iAllocCount = 0;
    pstTable->iActiveCount = 0;
    pstTable->iFreeCount = 0;
}

/******************************************************************************
  函数名：createTmr
  功能描述：
  创建一个定时器，并加入到定时器表中 

  输入参数：
    TIMERS *pstTable 定时器表  
    struct timeval *pstNow 当前时间,可为NULL 
    procTimer *pfnProcTimer 定时器回调函数
    TIMER_DATA *  stTimerData  回调函数所需数据
    long dwMsecs     定时器的间隔的毫秒数
    int iPeriodic      是周期还是一次性的定时器,可用宏,ONE_SHOT,PERIODIC
  输出参数：
    无

  返回值：
    TIMER * 返回定时器指针
 *****************************************************************************/
TIMER *createTmr(
        TIMERS *pstTable, struct timeval* pstNow, procTimer* pfnProcTimer, TIMER_DATA stTimerData,
        long dwMsecs, int iPeriodic )
{
    TIMER* pstTemp;

    if ( pstTable->pstFreeTimers != (TIMER*) 0 )
    {
        pstTemp = pstTable->pstFreeTimers;
        pstTable->pstFreeTimers = pstTemp->pstNext;
        --pstTable->iFreeCount;
    }
    else
    {
        pstTemp = (TIMER*) malloc( sizeof(TIMER) );
        if ( pstTemp == (TIMER*) 0 )
            return (TIMER*) 0;
        ++pstTable->iAllocCount;
    }

    pstTemp->pfnProcTimer = pfnProcTimer;
    pstTemp->stTimerData = stTimerData;
    pstTemp->dwMsecs = dwMsecs;
    pstTemp->iPeriodic = iPeriodic;
    if ( pstNow != (struct timeval*) 0 )
        pstTemp->stTime = *pstNow;
    else
        (void) gettimeofday( &pstTemp->stTime, (struct timezone*) 0 );
    pstTemp->stTime.tv_sec += dwMsecs / 1000L;
    pstTemp->stTime.tv_usec += ( dwMsecs % 1000L ) * 1000L;
    if ( pstTemp->stTime.tv_usec >= 1000000L )
    {
        pstTemp->stTime.tv_sec += pstTemp->stTime.tv_usec / 1000000L;
        pstTemp->stTime.tv_usec %= 1000000L;
    }
    pstTemp->iHash = hash(pstTable, pstTemp );
    /* Add the new timer to the proper active list. */
    addLink(pstTable,pstTemp );
    ++pstTable->iActiveCount;

    return pstTemp;
}


/******************************************************************************
  函数名：TIMERS *timeoutTmr
  功能描述：
  确定定时器表中最先超时的定时器

  输入参数：
  TIMERS *pstTable 定时器表  
  struct timeval *  当前时间 

  输出参数：
  无 

  返回值：
  struct timeval * 
 *****************************************************************************/

struct timeval* timeoutTmr( TIMERS *pstTable, struct timeval* pstNow )
{
    long dwMsecs;
    static struct timeval timeout;

    dwMsecs = mstimeoutTmr(pstTable, pstNow );
    if ( dwMsecs == INFTIM )
        return (struct timeval*) 0;
    timeout.tv_sec = dwMsecs / 1000L;
    timeout.tv_usec = ( dwMsecs % 1000L ) * 1000L;
    return &timeout;
}


/******************************************************************************
  函数名：TIMERS *mstimeoutTmr
  功能描述：
  确定定时器表中最先超时的定时器

  输入参数：
  TIMERS *pstTable 定时器表  
  struct timeval * 当前时间 

  输出参数：
  无 

  返回值：
  long, 返回0表示已经有定时器超时，非0则表示最先超时的定时器所需毫秒数  
 *****************************************************************************/
long mstimeoutTmr(TIMERS *pstTable,  struct timeval* pstNow )
{
    int h;
    int gotone;
    long dwMsecs, m;
    register TIMER* pstTemp;

    gotone = 0;
    dwMsecs = 0;          /* make lint happy */
    /* Since the lists are sorted, we only need to look at the
     ** first timer on each one.
     */
    for ( h = 0; h < pstTable->iSize; ++h )
    {
        pstTemp = pstTable->pstTimersTable[h];
        if ( pstTemp != (TIMER*) 0 )
        {
            m = ( pstTemp->stTime.tv_sec - pstNow->tv_sec ) * 1000L +
                ( pstTemp->stTime.tv_usec - pstNow->tv_usec ) / 1000L;
            if ( ! gotone )
            {
                dwMsecs = m;
                gotone = 1;
            }
            else if ( m < dwMsecs )
                dwMsecs = m;
        }
    }
    if ( ! gotone )
        return INFTIM;
    if ( dwMsecs <= 0 )
        dwMsecs = 0;
    return dwMsecs;
}

/******************************************************************************
  函数名：runTmr
  功能描述：
   遍历定时器表，运行已超时的定时器 

  输入参数：
    TIMERS *pstTable 定时器表  
    struct timeval *  当前时间 

  输出参数：
    无 

  返回值：
    无 
 *****************************************************************************/
void runTmr( TIMERS *pstTable, struct timeval* pstNow )
{
    int h;
    TIMER* pstTemp;
    TIMER* pstNext;

    for ( h = 0; h < pstTable->iSize; ++h )
        for ( pstTemp = pstTable->pstTimersTable[h]; pstTemp != (TIMER*) 0; pstTemp = pstNext )
        {
            pstNext = pstTemp->pstNext;
            /* Since the lists are sorted, as soon as we find a timer
             ** that isn'pstTemp ready yet, we can go on to the next list.
             */
            if ( pstTemp->stTime.tv_sec > pstNow->tv_sec ||
                    ( pstTemp->stTime.tv_sec == pstNow->tv_sec &&
                      pstTemp->stTime.tv_usec > pstNow->tv_usec ) )
                break;
            (pstTemp->pfnProcTimer)( pstTemp->stTimerData, pstNow );
            if ( pstTemp->iPeriodic )
            {
                /* Reschedule. */
                pstTemp->stTime.tv_sec += pstTemp->dwMsecs / 1000L;
                pstTemp->stTime.tv_usec += ( pstTemp->dwMsecs % 1000L ) * 1000L;
                if ( pstTemp->stTime.tv_usec >= 1000000L )
                {
                    pstTemp->stTime.tv_sec += pstTemp->stTime.tv_usec / 1000000L;
                    pstTemp->stTime.tv_usec %= 1000000L;
                }
                resortLink( pstTable,pstTemp );
            }
            else
                cancelTmr(pstTable, pstTemp );
        }
}

/******************************************************************************
  函数名：resetTmr
  功能描述：
    重置定时器 

  输入参数：
    TIMERS *pstTable 定时器表  
    struct timeval  *pstNow 当前时间 
    TIMER *pstTemp 需重置的定时器

  输出参数：
    无 

  返回值：
    无 
 *****************************************************************************/
void resetTmr( TIMERS *pstTable, struct timeval* pstNow, TIMER* pstTemp )
{
    pstTemp->stTime = *pstNow;
    pstTemp->stTime.tv_sec += pstTemp->dwMsecs / 1000L;
    pstTemp->stTime.tv_usec += ( pstTemp->dwMsecs % 1000L ) * 1000L;
    if ( pstTemp->stTime.tv_usec >= 1000000L )
    {
        pstTemp->stTime.tv_sec += pstTemp->stTime.tv_usec / 1000000L;
        pstTemp->stTime.tv_usec %= 1000000L;
    }
    resortLink( pstTable,pstTemp );
}

/******************************************************************************
  函数名：cancelTmr
  功能描述：
   取消某个定时器，一般用于取消某个周期性定时器，一次性的在运行后自动取消 

  输入参数：
    TIMERS *pstTable 定时器表  
    TIMER *pstTemp 需取消的定时器

  输出参数：
    无 

  返回值：
    无 
 *****************************************************************************/
void cancelTmr(TIMERS *pstTable, TIMER* pstTemp )
{
    /* Remove it from its active list. */
    removeLink(pstTable, pstTemp );
    --pstTable->iActiveCount;
    /* And put it on the free list. */
    pstTemp->pstNext = pstTable->pstFreeTimers;
    pstTable->pstFreeTimers = pstTemp;
    ++pstTable->iFreeCount;
    pstTemp->pstPrev = (TIMER*) 0;
}

/******************************************************************************
  函数名：cleanupTmr
  功能描述：
   释放无用的内存空间 

  输入参数：
    TIMERS *pstTable 定时器表  

  输出参数：
    无 

  返回值：
    无 
 *****************************************************************************/
void cleanupTmr( TIMERS *pstTable)
{
    TIMER* pstTemp;

    while ( pstTable->pstFreeTimers != (TIMER*) 0 )
    {
        pstTemp = pstTable->pstFreeTimers;
        pstTable->pstFreeTimers = pstTemp->pstNext;
        --pstTable->iFreeCount;
        free( (void*) pstTemp );
        --pstTable->iAllocCount;
    }
}

/******************************************************************************
  函数名：destroyTmr
  功能描述：
   清除所有定时表的空间

  输入参数：
    TIMERS *pstTable 定时器表  

  输出参数：
    无 

  返回值：
    无 
 *****************************************************************************/
void destroyTmr( TIMERS *pstTable)
{
    int h;

    for ( h = 0; h < pstTable->iSize; ++h )
        while ( pstTable->pstTimersTable[h] != (TIMER*) 0 )
            cancelTmr(pstTable, pstTable->pstTimersTable[h] );
    cleanupTmr(pstTable);
}

#if 0
/* Generate debugging statistics syslog message. */
void logStatsTmr( TIMERS *pstTable, long secs )
{
    syslog(
            LOG_INFO, "  timers - %d allocated, %d active, %d free",
            pstTable->iAllocCount, pstTable->iActiveCount, pstTable->iFreeCount );
    if ( pstTable->iActiveCount + pstTable->iFreeCount != pstTable->iAllocCount )
        syslog( LOG_ERR, "timer counts don'pstTemp add up!" );
}
#endif
